The present invention relates to methods and devices for handling transmission of data cells from a node, where the cells belong to different channels and are transmitted from a station in predetermined rates specific for each channel.
In the transmission of calls or messages in an asynchronous network each call or message is divided in short cells or segments which are forwarded in the network, each cell then belonging to a specific call or message or generally to a particular logical connection. These connections are established when the call is made or the request is made for transmitting a message, e.g. a digital file, through the network. Depending on the user or requester of the transmission, each logical connection is assigned a predetermined transmission rate which is a fraction of the total transmission rate of cells for the nodes in the network, the magnitude of the fraction implying different costs for the user or requester. There is then a problem of issuing the data cells in these rates from a station into the network so that these predetermined rates are not exceeded. The same problem can also exist in nodes inside the network, where the transmission rates of the different logical connections can have been unbalanced by the fact that the cells can pass through different paths, that buffers may be full and some cells are then discarded, etc.
In the published patent European application EP-A1 0 609 114 a method is disclosed for transmission of cells in an ATM-network. The method comprises a number of steps including that in one of the steps the cells are separated by a least time interval representing a known time resolution. In another step the cells are separated by a least time interval representing the maximum allowed transmission rates for the respective user. The time separation is performed by means of different timers. For each separation of the first kind the cells are collected in a number of files of cells or lists of cells, which are transmitted successively. In the other separation, the cells having different allowed maximum transmission rates are distributed over the files or lists, for each transmission rate evenly or with an equal spacing over files or lists.
In the published International patent application WO-A1 94/14266 a system is disclosed for controlling the flow of cells through nodes in an ATM-network. The switches of the system which are equipped with both input and output buffers can, by means of throttling, control the flow of cells from the input buffers if an addressed output buffer is overloaded. In an embodiment each output buffer has a device detecting its fill level, the detected value being reported continuously for controlling the throttling. The purpose of the throttling is here primarily only for preventing overload or overflow of the output buffers.
Other systems using throttling in networks are disclosed in U.S. Pat. No. 5,280,470 and the published European patent application EP-A2 0 573 739.
It is an object of the invention to provide methods and devices for handling transmission, from a considered point such as a station or node, of cells which belong to different logical connections, where all cells are transmitted at predetermined rates, the handling method and device requiring only simple hardware with an efficient use of memory areas.
In particular, it is an object of the invention to provide methods and devices for handling transmission of cells from a station or node, where predetermined rates, established for cells belonging to different logical connections, are not exceeded and cells are transmitted simultaneously from the station at the highest possible total rate.
In particular, it is a further object of the invention to provide methods and devices for handling transmission of cells from a station or node, where in the transmission of cells, in the case where the sum of predetermined rates, established for cells belonging to different logical connections, exceeds the total transmission rate of the station or node, or worded equivalently, exceeds the total transmission band width, all predetermined rates are decreased in a fair manner so that no connection will be more favoured than others, e.g. that no connection is blocked when the others are not, and in particular that all connections having the same predetermined rate are handled equally, none of them being given more transmission time than the others.
In particular, it is a still further object of the invention to provide methods and devices for handling transmission of cells from a point or station, where cells belonging to different logical connections or from different sources arrive to the station at different rates and at some time periods even no cells will arrive belonging to some connections, the transmission capacity is assigned to the connections based on their instantaneous needs, so that during those time periods, when there are cells ready to be transmitted a connection is given its share of the total transmission bandwidth, based on the predetermined rate of the connection, and in other cases when there are no cells, this bandwidth is used for transmitting cells from other connections, where the transmission from the connection is started rapidly thereafter when it has cells which are ready to be transmitted.
It is another object of the invention to provide methods and devices for transmission of cells from a station or node, where the transmission rates for cells belonging to different logical connections can be set with a high resolution and for every connection independent of all other connections.
It is a further object of the invention to provide methods and devices for transmission of cells from a station or node, where the transmission rate for cells belonging to a logical connection can be changed during the transmission of the cells.
It is a still further object of the invention to provide methods and devices for transmission of cells from a station or node, where the total handling time for handling the transmission of cells belonging to different logical connections will principally not increase, when the number of established logical connections increases, and where the amount of additional hardware required for the method and in the device is only moderate in the case, where the method and device are extended to handling more logical connections than before.
It is another object of the invention to provide methods and devices for handling transmission, from a station or node, of cells which belong to different logical connections, for which method and device all cells belonging to each connection are transmitted at a rate predetermined for each connection, the handling method and device giving a smooth cell flow out from the station or node.
Thus in a station or terminal for a network data cells are transmitted from the terminal and the cells are arranged to belong to different logical connections, which are derived from various logical or physical sources. Each source and thus connection is supposed to require a particular transmission rate, which is not to be exceeded and which can be changed. Then for each one of a number of successive time slots a queue is arranged, the first or current queue being the one which is pointed to by a pointer. The time slot queues comprise in a consecutive order, identifiers of those connections for which a data cell is to be transmitted, or they may in some special cases even contain the cells themselves. The first position in such a queue indicates the connection, for which a data cell is to be sent with the highest degree of priority. The following positions indicate connections which have lower degrees of priority in a decreasing order. The first or next data cell of the logical connection the identifier of which is the first one in the time slot queue as pointed to by the pointer is then transmitted from the station and an identifier of the same connection is added to that other queue which has a distance from the considered queue in the sequential order of queues, where this distance is calculated from the transmission rate which is particular for the connection, to which the transmitted cell belongs. After that the remaining part of the first queue is transferred to the next queue and placed in front of the all the items in this next queue. The first queue is thus empty and the pointer is stepped to point to this next queue.
Generally, data segments or cells are transmitted from a station, where each data segment preferably has the same length. Data are assumed to arrive at the station from various logical and/or physical sources or to belong to some logical connection. Each source is assumed to require or to been assigned a particular transmission rate for the data segments derived from the data arriving from this source, where this transmission rate is not to be exceeded for these data segments. The data segments are transmitted from the station one at a time and at successive times, in particular at periodic times.
For each one of successive times from a considered current time a logical or physical queue is arranged in special memory means provided therefor, where the first queue is the next or current one, as considered from the current time, the second queue is the queue immediately after the first, etc. Each of the queues comprises in a consecutive order, identifiers of those sources or connections for which a data segment of theirs is to be transmitted or it may instead contain the data segments themselves or addresses thereof, in the case where the actual segments are stored in some other memory means. The first position in such a queue indicates directly, or indirectly in the case where it contains a data segment or an address thereof respectively, the source or connection, for which a data segment is to be sent with the highest degree of priority, and the following, higher positions indicate sources which have lower degrees of priority in a decreasing order.
A first or next data segment from the source first indicated in the first queue or the first data segment in or as indicated first in the first queue is transmitted and after that the remaining part of the first queue is transferred, maintaining its internal successive order of queue items, to the next queue and placing it in front of all the items possibly already present in this next queue. Then the first queue is removed and the remaining queues are renumbered or moved, so that now the former second queue, the queue after the next one, will be the first one, etc. maintaining the sequential order of the queues.
Queues are preferably arranged for only a predetermined number of successive times and then, after the renumbering or moving of the remaining queues, a last queue is added to the set of queues, where this last queue is empty and in a cyclical way corresponds to the removed former first queue.
Also, an output buffer memory may be arranged and in this case, when a data segment is to be transmitted it is placed or an indication of the data segment is placed in the output buffer and then it is physically transmitted from the station and in this operation it or the indication thereof is retrieved and removed from the output buffer.
It may occur that the first queue is empty and then no data segment is transmitted. Obviously, a data segment could then be transmitted from the following queue, but it would violate the condition that the set transmission rates for the channels should not be exceeded, as will appear hereinafter. Instead, in the case where the first queue is empty, a special data segment or an indication thereof may be placed in the output buffer, this special data segment having such a construction or being such type that is easily recognized and will not be transmitted from the station.
The transmission from the station is preferably performed periodically, in uniformly distributed and equally long physical time slots, and then the transmission of data segments is made from the segments stored in or indicated in the output buffer sequentially, one segment at each of these periodically repeated times. In the case where the special data segment or an indication thereof is located at the next position in the output buffer where a data segment or an indication thereof should be stored and is to be transmitted, no data segment is transmitted at the corresponding periodic time. This may also be necessary for ensuring that the set transmission rates are not exceeded.
Immediately before or after the step of removing the first queue or after adding an empty last queue the following step is performed, which ensures generally the throttling. Then an identifier of the same data source or a next data segment or an address thereof from the same source, from which a data segment was transmitted, is added to that queue, which has a distance from the removed queue in the sequential order of queues, where this distance is determined from the transmission rate for the source, to which the data segment belongs. The addition is preferably made first in that queue.
In the case where a source or connection that has previously not had an identifier of itself or any of its data segments or addresses thereof in any queue, starts to be active, that is in the case where it gets at least one data segment to be transmitted from the station, an identifier of this source or connection or the next one of its data segments or an address thereof, is preferably added to the queue, which is the next one after the current one. The addition is preferably made last in that queue.
A station for carrying out the described steps then comprises transmission means for transmitting the data segments one at a time and at successive times, memory means for storing, for each one of successive times from a considered current time, a logical or physical queue, and suitably adapted control or processor means. The memory means may then be arranged for storing only a predetermined number of successive queues and in particular the memory means may be arranged for storing the queues in a cyclical manner and then a memory field is arranged to store a pointer pointing to a current one of the cyclically arranged queues. An output buffer can be provided for storing data segments or indications thereof before the actual transmission from the station. A special data segment or an indication thereof may be stored in a memory field arranged therefor to be copied to the output buffer to indicate an empty place, where so required, so that the transmission means will not, when this special data segment is found in the output buffer, transmit any data segment from the station. A memory field may be provided for each source or connection to hold a distance value or number determined from the transmission rate for the source.
In the case where the memory means for the queues comprise identifiers of sources, the memory means for storing the source identifiers are advantageously arranged as a linked list, including first memory means comprising fields for storing the first items in each queue, second memory means comprising fields for storing the last items in each queue and third memory means comprising fields in a sequential order. Each field in the third memory means has a sequential order number and they are arranged for storing next items in the queues, so that the sequential order number of a field indicates the item immediately before the item stored in the field.